package algorithm;

public class leetcode_0304 {
    class NumMatrix {

        private int[][] matrix;
        private int[][] pre;

        public NumMatrix(int[][] matrix) {
            this.matrix = matrix;
            this.pre = new int[matrix.length+1][matrix[0].length+1];
            for(int i=1;i< matrix.length+1;++i){
                for(int j=1;j<matrix[0].length+1;++j){
                    pre[i][j] = pre[i-1][j]+pre[i][j-1] -pre[i-1][j-1]+matrix[i-1][j-1];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return pre[row2+1][col2+1] + pre[row1][col1] - pre[row2+1][col1] - pre[row1][col2+1];
        }
    }
}
